home *** CD-ROM | disk | FTP | other *** search
/ Aminet 35 / Aminet 35 (2000)(Schatztruhe)[!][Feb 2000].iso / Aminet / game / shoot / ADescentSrc.lha / descent / main / hash.c < prev    next >
C/C++ Source or Header  |  1998-04-24  |  4KB  |  172 lines
  1. /*
  2. THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
  3. SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
  4. END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
  5. ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
  6. IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
  7. SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
  8. FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  9. CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10. AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.  
  11. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12. */
  13. /*
  14.  * $Source: /usr/CVS/descent/main/hash.c,v $
  15.  * $Revision: 1.3 $
  16.  * $Author: tfrieden $
  17.  * $Date: 1998/04/24 14:27:51 $
  18.  * 
  19.  * Functions to do hash table lookup.
  20.  * 
  21.  * $Log: hash.c,v $
  22.  * Revision 1.3  1998/04/24 14:27:51  tfrieden
  23.  * Debug
  24.  *
  25.  * Revision 1.2  1998/03/22 16:07:04  hfrieden
  26.  * What the hell did I do here? CVS says Locally Modified?
  27.  *
  28.  * Revision 1.1.1.1  1998/03/03 15:12:23  nobody
  29.  * reimport after crash from backup
  30.  *
  31.  * Revision 1.1.1.1  1998/02/13  20:20:55  hfrieden
  32.  * Initial Import
  33.  *
  34.  * Revision 2.0  1995/02/27  11:28:01  john
  35.  * New version 2.0, which has no anonymous unions, builds with
  36.  * Watcom 10.0, and doesn't require parsing BITMAPS.TBL.
  37.  * 
  38.  * Revision 1.5  1994/12/05  23:37:06  matt
  39.  * Took out calls to warning() function
  40.  * 
  41.  * Revision 1.4  1994/05/09  20:02:33  john
  42.  * Fixed bug w/ upper/lower case.
  43.  * 
  44.  * Revision 1.3  1994/05/06  15:31:51  john
  45.  * Don't add duplicate names to the hash table.
  46.  * 
  47.  * Revision 1.2  1994/05/03  16:45:35  john
  48.  * Added hash table lookup to speed up loading.
  49.  * 
  50.  * Revision 1.1  1994/05/03  10:36:41  john
  51.  * Initial revision
  52.  * 
  53.  * 
  54.  */
  55.  
  56. #pragma off (unreferenced)
  57. static char rcsid[] = "$Id: hash.c,v 1.3 1998/04/24 14:27:51 tfrieden Exp $";
  58. #pragma on (unreferenced)
  59.  
  60. #include <stdlib.h>
  61. #include <stdio.h>
  62. #include <string.h>
  63.  
  64. #include "error.h"
  65. #include "mono.h"
  66. #include "hash.h"
  67. #include "key.h"
  68.  
  69. extern int Inferno_verbose;
  70.     
  71. int hashtable_init( hashtable *ht, int size )   {
  72.     int i;
  73.  
  74.     ht->size=0;
  75.  
  76.  
  77.     for (i=1; i<16; i++ )   {   // CHANGED: Was 13
  78.         if ( (1<<i) >= size )   {
  79.             ht->bitsize = i;
  80.             ht->size = 1<<i;
  81.             break;
  82.         }
  83.     }
  84.     size = ht->size;
  85.     ht->and_mask = ht->size - 1;
  86.     if (ht->size==0)
  87.         Error( "Hashtable has size of 0" );
  88.  
  89.     ht->key = (char **)calloc(1, size * sizeof(char *) ); // CHANGED: was malloc
  90.     if (ht->key==NULL)
  91.         Error( "Not enough memory to create a hash table of size %d", size );
  92.  
  93.     for (i=0; i<size; i++ )
  94.         ht->key[i] = NULL;
  95.  
  96.     // Use calloc cause we want zero'd array.
  97.     ht->value = calloc(1, size*sizeof(int) );     // CHANGED: was malloc
  98.     if (ht->value==NULL)    {
  99.         free(ht->key);
  100.         Error( "Not enough memory to create a hash table of size %d\n", size );
  101.     }
  102.  
  103.     ht->nitems = 0;
  104.  
  105.     if (Inferno_verbose) printf("Creating hashtable, size %d(%d)\n", size, ht->bitsize);
  106.  
  107.     return 0;
  108. }
  109.  
  110. void hashtable_free( hashtable *ht )    {
  111.     if (ht->key != NULL )
  112.         free( ht->key );
  113.     if (ht->value != NULL )
  114.         free( ht->value );
  115.     ht->size = 0;
  116. }
  117.  
  118. int hashtable_getkey( char *key )   {
  119.     int k = 0, i=0;
  120.  
  121.     while( *key )   {
  122.         k^=((int)(*key++))<<i;
  123.         i++;
  124.     }
  125.     return k;
  126. }
  127.  
  128. int hashtable_search( hashtable *ht, char *key )    {
  129.     int i,j,k;
  130.  
  131.     strlwr( key );
  132.  
  133.     k = hashtable_getkey( key );
  134.     i = 0;
  135.     
  136.     while(i < ht->size )    {
  137.         j = (k+(i++)) & ht->and_mask;
  138.         if ( ht->key[j] == NULL )
  139.             return -1;
  140.         if (!stricmp(ht->key[j], key ))
  141.             return ht->value[j];
  142.     }
  143.     return -1;
  144. }
  145.  
  146. void hashtable_insert( hashtable *ht, char *key, int value )    {
  147.     int i,j,k;
  148.  
  149. //  mprintf( 0, "Inserting '%s' into hash table\n", key );
  150. //  key_getch();
  151.  
  152.     strlwr( key );
  153.     k = hashtable_getkey( key );
  154.     i = 0;
  155.  
  156.     while(i < ht->size) {
  157.         j = (k+(i++)) & ht->and_mask;
  158. //      Assert( j < ht->size );
  159. //      mprintf( 0, "Word '%s' (%d) at level %d has value of %d\n", key, k, i-1, j );
  160. //      mprintf( 0, "ht->key[%d]=%.8x\n", j, ht->key[j] );
  161.         if ( ht->key[j] == NULL )   {
  162.             ht->nitems++;
  163.             ht->key[j] = key;
  164.             ht->value[j] = value;
  165.             return;
  166.         } else if (!stricmp( key, ht->key[j] )) {
  167.             return;
  168.         }
  169.     }
  170.     Error( "Out of hash slots (%d)\n", ht->size );
  171. }
  172.